'''
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
示例 3：
输入：s = "a"
输出："a"
示例 4：
输入：s = "ac"
输出："a"
提示：
1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成
'''
# from _typeshed import Self


class Solution:
    def longestPalindrome(self, s: str) -> str:
        # dp动态规划算法
        palindrome =''
        for i in range(len(s)):
            len1 = len(self.getlongpalindrome(s,i,i))
            if len1 > len(palindrome):
                palindrome = self.getlongpalindrome(s,i,i)
            len2  = len(self.getlongpalindrome(s,i,i+1))
            if len2 > len(palindrome):
                palindrome=self.getlongpalindrome(s,i,i+1)
        return palindrome
    def getlongpalindrome(self,s,l,r):
        while l >=0 and r <len(s) and s[l]==s[r]:
            l-=1
            r+=1
        return s[l+1:r]

## 方法二：最长子序列问题的方法二
# babad
# 
# 
# 
    def longestPalindrome(self, s: str) -> str:
        length =len(s)
        if length <2:
            return s
        # 定义状态转移矩阵
        dp = [[False for _ in range(length)] for _ in range(length)]
        max_len = 1
        start = 0
        for j in range(1,length):
            for i in range(j):
                if s[i]==s[j]:
                    if j-i <3:
                        dp[i][j]=True
                    else:
                        dp[i][j] = dp[i+1][j-1]
                if dp[i][j]:
                    cur_len = j-i+1
                    if cur_len > max_len:
                        max_len = cur_len
                        start = i
        return s[start:start+max_len]        



if __name__=="__main__":
    palindrome= Solution()
    pa = palindrome.longestPalindrome("cbabd")
    print(pa)